package com.lans.binary;

/**
 * @author: lans
 * @date: 2025/2/28
 * @name: 刘宇
 */
public class HeapSort{
    /*
            设计两个数组
                原数组:构造堆的元素所存放的数组
                堆数组:实现堆结构的数组
     */
    //创建堆数组
    public static void createHeap(Comparable[]heap,Comparable[] source){
        //拷贝数组
        System.arraycopy(source,0,heap,1,source.length);
        for(int i = (heap.length)/2;i>0;i--){
            //下沉调整位置
            sink(heap,i,heap.length-1);
        }
    }

    public static void sort(Comparable[] source){
        Comparable[] heap = new Comparable[source.length + 1];
        createHeap(heap,source);
        int N = heap.length-1;
        while(N!=1){
            exch(heap,1,N);
            N--;
            sink(heap,1,N);
        }
        System.arraycopy(heap,1,source,0,source.length);
    }

    /**
     *
     * @param heap
     * @param target 目标节点位置
     * @param range 截止到节点为止
     */
    public static void sink(Comparable[] heap,int target,int range){
        int max;
        while(2*target<=range){
            if(2*target+1<=range){
                if(less(heap,2*target,2*target+1)){
                    max = 2*target+1;
                }else{
                    max = 2*target;
                }
            }else{
                max  = 2*target;
            }
            if(!less(heap,target,max)){
                break;
            }
            exch(heap,target,max);
            target = max;
        }
    }

    //判断索引处 i处的元素是否小于j处的元素
    public static boolean less(Comparable[] heap,int i,int j){
        return heap[i].compareTo(heap[j]) < 0;
    }
    //交换位置
    public static void exch(Comparable[] heap,int i,int j){
        Comparable temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}